﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

//project check

public class Drzewo
{
    private int licz = 0;
    private int poziomy;
    private int[][] drabinka;
    public Drzewo(ref int[] wartosci) // konstruktor, brane sa klucze z tablicy elementów np. pakietow
    {
        /*poziomy = (int)Math.Log(wartosci.Length, 2);
        int[][] drabinka = new int[poziomy+1][];
        drabinka[0] = new int[wartosci.Length];
        for (int i = 0; i < wartosci.Length; i++)
        {
            drabinka[0][i] = wartosci[i];
        }*/
    }


    
    public int[][] turniej(ref int[] wartosci) // funckja przeprowadzajaca turniej
    {
        double nastepny = 0; // ilosc elementow w nastepnym poziomie (wyzej)
        int i = 0;
        poziomy = (int)Math.Log(wartosci.Length, 2)+1; // obliczona laczna ilosc poziomow

        drabinka = new int[poziomy+1][]; // deklaracja liczby poziomow drabinki (wierszy)
        drabinka[0] = new int[wartosci.Length]; // stworzenie liczby miejsc w wierszu 0 dla wszystkich wartosci klucza

        for (i = 0; i < wartosci.Length; i++) // kopiowanie wartosci kluczy z tablicy do drzewa
        {
            drabinka[0][i] = wartosci[i];
        }

        nastepny = (double)drabinka[0].Length / 2; // obliczanie ilosci elementow na kolejnym poziomie
        nastepny = Math.Ceiling((double)nastepny);
        drabinka[1] = new int[(int)nastepny]; // deklaracja liczby miejsc w poziomie 1

        nastepny = drabinka[0].Length; // ilosc elementow w wierszu 0
        i = 0;

        for (int j = 0; j < poziomy; j++)
        {
            while (i < nastepny)
            {
                if (i == (drabinka[j].Length-1)) // jesli jest to ostatni element na danym poziomie
                {
                    drabinka[j + 1][licz] = drabinka[j][i];
                    licz++;
                    i += 2;
                    continue;
                }

                if (drabinka[j][i] > drabinka[j][i + 1]) // jesli element i jest wiekszy od i+1
                {
                    drabinka[j + 1][licz] = drabinka[j][i + 1];
                    licz++;
                    i += 2; // przejdz do elementu i+2
                }
                else
                {
                    drabinka[j + 1][licz] = drabinka[j][i];
                    licz++;
                    i += 2;
                }
            }

            if (j + 2 == poziomy) // jesli deklarujemy miejsce na ostatni poziom to tworzymy tylko jedno miejsce
            {
                drabinka[j + 2] = new int[1];
            }
            if((j+2) < poziomy){ // jesli deklarujemy na poziom niższy od liczby poziomow
                nastepny = (double)licz/2; // wyliczanie ilosc elementow na ten poziom (j+2)
                nastepny = Math.Ceiling((double)nastepny);
                drabinka[j + 2] = new int[(int)nastepny];
            }
            nastepny = licz;
            licz = 0;
            i = 0;

        }
        return drabinka; // zwracanie tablicy
    }
}

namespace Drzewo_turniejowe
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] tab = new int[15] { 5, 5, 1, 3, 2, 8, 6, 7, 9, 0, 1, 12, 3, 5, 6 };
            //Bubble bubble = new Bubble();
            //bubble.sort(ref tab);
            //bubble.print(ref tab);
            Drzewo drzewo = new Drzewo(ref tab);
            int[][] drabinka = drzewo.turniej(ref tab);
            Console.WriteLine("Liczba zamian wyniosla: ");
            for (int i = 0; i < drabinka.Length; i++)
            {
                for (int j = 0; j < drabinka[i].Length; j++)
                {
                    Console.Write(drabinka[i][j] + " ");
                }
                Console.WriteLine();
            }
                Console.ReadLine();
        }
    }
}
